翻訳と辞書 Words near each other ・ Bach Prelude and Fugue No. 16 ・ Bach quadrangle ・ Bach Society Orchestra of Harvard University ・ Bach suites ・ Bach Super Transport ・ Bach Technology ・ Bach tensor ・ Bach to the Blues ・ Bach v Longman ・ Bach Vespers at Westminster ・ Bach vom Schlüsselgrund ・ Bach von dem Kohl ・ Bach von dem Vierstöck ・ Bach von den Rehwiesen ・ Bach von der Dickhecke ・ Bach's algorithm ・ Bach's Bottom ・ Bach's church music in Latin ・ Bach's Fight for Freedom ・ Bach's Greatest Hits ・ Bach's Nekrolog ・ Bach, Austria ・ Bach, Lot ・ Bach-Busoni Editions ・ Bach-Collegium Stuttgart ・ Bach-Elgar Choir ・ Bach-Werke-Verzeichnis ・ BACH1 ・ BACH2 ・ Bacha Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Bach's algorithm ： ウィキペディア英語版 Bach's algorithm Bach's algorithm〔Bach, Eric. ''How to Generate Factored Random Numbers'', SIAM Journal of Computing, 17 (1988), pp 179-193.〕 is a probabilistic polynomial time algorithm for generating random numbers along with their factorization, named after its discoverer, Eric Bach. It is of interest because no algorithm is known that efficiently factors numbers, so the straightforward method, namely generating a random number and then factoring it, is impractical. The algorithm performs, in expectation, O(log n) primality tests. A simpler, but less efficient algorithm (performing, in expectation, O(log2 n) primality tests), is known and is due to Adam Kalai〔Generating Random Factored Numbers, Easily: Adam Kalai, Journal of Cryptology, Vol 16, Number 4, 2003〕 == Overview == Bach's algorithm produces a number ''x'' uniformly at random between a given limit ''N'' and ''N''/2, specifically , along with its factorization. It does this by picking a prime number ''p'' and an exponent ''a'' such that $p^a\; \backslash le\; N$, according to a certain distribution. Bach's algorithm is then recursively applied to generate a number ''y'' uniformly at random between ''M'' and ''M''/2, where $M\; =\; \backslash frac$, along with the factorization of ''y''. It then sets $x\; =\; p^y$, and appends $p^a$ to the factorization of ''y'' to produce the factorization of ''x''. This gives ''x'' which logarithmic distribution over the desired range; rejection sampling is then used to get a uniform distribution. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Bach's algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.